#include <iostream>
#include <stdlib.h>
#include <time.h>

using namespace std;

// 递归二分查找
// 1.函数用来查找数字中是否包含val值，是则返回索引，否则返回-1
// 2.递归需要增加边界条件，当左边界大于右边界时，返回-1
// 3.递归只考虑横向查找，纵向查找交给递归
int binarySearch(int arr[], int l, int r, int val)
{
    if (l > r)
        return -1;

    int mid = (l + r) / 2;
    if (arr[mid] == val)
        return mid;
    else if (arr[mid] > val)
        return binarySearch(arr,l,mid-1,val);
    else
        return binarySearch(arr,mid+1,r,val);
}

int main(int argc, const char** argv) {
    int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    // srand(time(NULL));

    // for (int i = 0; i < 10; i++) {
    //     arr[i] = rand() % 100;
    //     cout << arr[i] << " ";
    // }
    // cout << endl;

    int index = binarySearch(arr, 0, 9, 5);
    cout << "index=" << index << endl;
    return 0;
}